package net.projecteuler.prob;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import org.jgrapht.DirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

import net.projecteuler.util.DigitUtil;

public class Problem61 implements Runnable{
	
	private class Figrative{
		int value;
		int figClass;
		
		public Figrative(int value, int figClass){
			this.value = value;
			this.figClass = figClass;
		}
		
		public String toString(){
			return value + "(" + figClass + ")";
		}
	}

	private List<Figrative> triList = new ArrayList<Figrative>();
	private List<Figrative> squareList = new ArrayList<Figrative>();
	private List<Figrative> pentaList = new ArrayList<Figrative>();
	private List<Figrative> hexaList = new ArrayList<Figrative>();
	private List<Figrative> heptaList = new ArrayList<Figrative>();
	private List<Figrative> octaList = new ArrayList<Figrative>();

	private DirectedGraph<Figrative, DefaultEdge> figGraph;
	
	private Figrative[] figCheck = new Figrative[8+1];
	int firstFigClass = 0;
	
	@Override
	public void run() {
		// TODO Auto-generated method stub
		System.out.println("Generating figurative list");
		fillFigLists();

		System.out.println("Generating figurative graph");
		figGraph = new DefaultDirectedGraph<Figrative, DefaultEdge>(DefaultEdge.class);
	
		for(int i = 3; i <= 8; i++){
			List<Figrative> figList = getFigList(i);
			for(int j = 0; j < figList.size(); j++)
				figGraph.addVertex(figList.get(j));
		}
		
		for(int f1 = 3; f1 <= 8; f1++){
			List<Figrative> figList1 = getFigList(f1);
			int figCnt1 = figList1.size();
			for(int i1 = 0; i1 < figCnt1; i1++){
				Figrative fig1 = figList1.get(i1);
				
				for(int f2 = 3; f2 <= 8; f2++){
					if(f1 == f2)
						continue;
					
					List<Figrative> figList2 = getFigList(f2);
					int figCnt2 = figList2.size();
					for(int i2 = 0; i2 < figCnt2; i2++){
						Figrative fig2 = figList2.get(i2);
						
						if(digitCont(fig1.value, fig2.value)){
							figGraph.addEdge(fig1, fig2);
						}
					}
				}
			}
		}

		System.out.println("Find cycle!");
		List<Figrative> triList = getFigList(3);
		for(int i = 0; i < triList.size(); i++){
			Figrative fig = triList.get(i);
			firstFigClass = fig.figClass;
			findCyclic(1, fig);
		}

		System.out.println("Done!");
		return;
	}

	private boolean findCyclic(int vertexCnt, Figrative vertex){
		if(figCheck[vertex.figClass] != null)
			return false;
		
		int success = 0;
		figCheck[vertex.figClass] = vertex;
		
		if(vertexCnt < 6){
			Set<DefaultEdge> edgeSet = figGraph.outgoingEdgesOf(vertex);
			for(Iterator<DefaultEdge> it = edgeSet.iterator(); it.hasNext(); ){
				DefaultEdge edge = it.next();
				Figrative vertex2 = figGraph.getEdgeTarget(edge);
				if(findCyclic(vertexCnt + 1, vertex2))
					success++;
			}
		} else {
			if(digitCont(vertex.value, figCheck[firstFigClass].value))
				success++;
		}
		
		figCheck[vertex.figClass] = null;
		if(success > 0){
			String str = "";
			for(int i = 1; i < vertexCnt; i++)
				str += "#";
			System.out.println(str + vertex);
			return true;
		}
		
		return false;
	}
	
	private List<Figrative> getFigList(int fig){
		List<Figrative> figList = null;
		switch(fig){
		case 3:
			figList = triList;
			break;
		case 4:
			figList = squareList;
			break;
		case 5:
			figList = pentaList;
			break;
		case 6:
			figList = hexaList;
			break;
		case 7:
			figList = heptaList;
			break;
		case 8:
			figList = octaList;
			break;
		}
		return figList;
	}

	private void fillFigLists(){
		List<Figrative> figList = null;
		
		for(int fig = 3; fig <= 8; fig++){
			figList = getFigList(fig);
			
			boolean bFourDigit = false;
			int n = 0;
			while(true){
				int num = getFigNum(fig, ++n);
				if(!bFourDigit && num > 1000)
					bFourDigit = true;
				if(bFourDigit){
					if(num > 9999)
						break;
					figList.add(new Figrative(num, fig));
				}
			}
		}
	}
	
	private boolean digitCont(int a, int b){
		int[] digitA = DigitUtil.digits(a);
		int[] digitB = DigitUtil.digits(b);
		
		if(digitA[0] == digitB[2] && digitA[1] == digitB[3])
			return true;
		
		return false;
	}
	
	private int getFigNum(int fig, int n){
		switch(fig){
		case 3:
			return getTriNum(n);
		case 4:
			return getSquare(n);
		case 5:
			return getPentaNum(n);
		case 6:
			return getHexaNum(n);
		case 7:
			return getHeptaNum(n);
		case 8:
			return getOctaNum(n);
		}
		
		return 0;
	}
	
	private int getTriNum(int n){
		return n * (n-1) / 2;
	}
	
	private int getSquare(int n){
		return n * n;
	}
	
	private int getPentaNum(int n){
		return n * (3 * n - 1) / 2;
	}
	
	private int getHexaNum(int n){
		return n * (2 * n - 1);
	}
	
	private int getHeptaNum(int n){
		return n * (5 * n - 3) / 2;
	}
	
	private int getOctaNum(int n){
		return n * (3 * n - 2);
	}

}
